Tipos de datos estructurados (página 2)

Partes: 1, 2

13
Ordenamiento Burbuja
Algoritmo
Arreglos Unidimensionales
PROGRAM Ordenamiento_Burbuja;
CONST
Largo = 5;
VAR
A: ARRAY[1..Largo] OF INTEGER;
i,j: INTEGER;
BEGIN
FOR i:=1 TO Largo DO
BEGIN
WRITE(‘Ingrese elemento ’,i,‘ : ’);
READLN(A[i])
END;
FOR i:=Largo DOWNTO 2 DO
FOR j:=1 TO i-1 DO
IF A[j] > A[j+1] THEN
Intercambiar(A[j],A[j+1]);
FOR i:=1 TO Largo DO
WRITELNA(A[i])
END.
(Gp:) i: indica la cantidad de casillas a comparar en cada vuelta.
j: indica la cantidad de compa-
raciones que se hacen por vuelta.

14
Búsqueda
Existen numerosos métodos para buscar un dato entre los elementos de un arreglo, algunos más rápidos que otros.

Por ejemplo, el método “carretero” consiste en comparar uno a uno el dato buscado con cada elemento del arreglo.

Escriba un programa que busque la posición en la que se encuentra el entero 15, dentro de un arreglo que contiene (ordenadamente) los números: 3,6,7,10,15,17,18 (7 en total)
(solución en diapositiva siguiente)
Arreglos Unidimensionales

15
PROGRAM busqueda_carretera;
CONST Largo = 15;
TYPE vector = ARRAY[1..Largo] OF INTEGER;
VAR X: vector; i, pos, num: INTEGER;
FUNCTION buscar(A: vector; dato: INTEGER): INTEGER;
VAR
j: INTEGER;
BEGIN
j := 1;
WHILE (j < = Largo) AND (A[j] < > dato) DO
j := j + 1;
buscar := j
END;
BEGIN
FOR i := 1 TO Largo DO
BEGIN
WRITE(‘Ingrese número: ’);
READLN(X[i])
END
WRITE(‘Ingrese número a buscar: ’);
READLN(num);
pos := buscar(X, num);
IF pos > Largo THEN WRITELN(‘No se encuentra el número’)
ELSE WRITELN(‘El número ’,num,’ está en la posición ’, pos)
END.
Búsqueda
…solución
Arreglos Unidimensionales
(Gp:) Función que implementa
la búsqueda carretera.

16
Búsqueda Binaria
Este algoritmo permite buscar un dato entre los elementos de un arreglo considerablemente más rápido que la búsqueda carretera.
Se basa en subdividir progresivamente el arreglo en 2 partes, buscando en aquella donde se encuentre el número. El arreglo donde se buscará debe estar ordenado. Ejemplo:
Arreglos Unidimensionales
medio
Si A[Medio] = 15, entonces Encontrado = TRUE
Si A[Medio] < 15, entonces Primero = Medio + 1
Si A[Medio] > 15, entonces Ultimo = Medio – 1
medio
(Gp:) Encontrado = TRUE

(Gp:) 3
(Gp:) 6
(Gp:) 7
(Gp:) 10
(Gp:) 15
(Gp:) 17
(Gp:) 18
(Gp:) primero
(Gp:) último
(Gp:) A

(Gp:) 3
(Gp:) 6
(Gp:) 7
(Gp:) 10
(Gp:) 15
(Gp:) 17
(Gp:) 18
(Gp:) primero
(Gp:) último
(Gp:) A

(Gp:) 3
(Gp:) 6
(Gp:) 7
(Gp:) 10
(Gp:) 15
(Gp:) 17
(Gp:) 18
(Gp:) primero, ultimo, medio
(Gp:) A

17
Búsqueda Binaria
…solución
Arreglos Unidimensionales
FUNCTION busqueda_binaria(A: vector; dato: INTEGER): INTEGER;
VAR primero, ultimo, medio: INTEGER; encontrado: BOOLEAN;
BEGIN
primero := 1;
ultimo := Largo;
encontrado := FALSE;
WHILE (primero < = ultimo) AND NOT(encontrado) DO
BEGIN
medio := (primero + ultimo) DIV 2;
IF A[medio] = dato THEN encontrado := TRUE
ELSE IF A[medio] < dato THEN primero := medio + 1
ELSE ultimo := medio – 1
END;
IF encontrado THEN busqueda_binaria := medio
ELSE busqueda_binaria = -1
END;
Escribiremos sólo la función busqueda_binaria.

18
Arreglos Bidimensionales
(Gp:) 1
(Gp:) 2
(Gp:) N
(Gp:) 1
(Gp:) 2
(Gp:) M
(Gp:) Declaración:
TYPE matriz = ARRAY[1..N,1..M] OF REAL;
VAR A: matriz;

Asignación: A[i,j] := valor;
Los arreglos bidimensionales se caracterizan por tener dos índices, representando una matriz.

19
Recorrido: el recorrido se efectúa con 2 FOR anidados, y se puede hacer de dos maneras.
Arreglos Bidimensionales
(Gp:) 1) FOR i := 1 TO N
FOR j := 1 TO M
READLN(A[i,j])
(Gp:) x
(Gp:) x
(Gp:) x
(Gp:) x
(Gp:) 1
(Gp:) 2
(Gp:) N
(Gp:) 1
(Gp:) 2
(Gp:) M
(Gp:) i
(Gp:) j
(Gp:) Recorrido hacia el lado,
se va llenando el arreglo
por filas.

(Gp:) 2) FOR j := 1 TO M
FOR i := 1 TO N
READLN(A[i,j])
(Gp:) x
(Gp:) x
(Gp:) x
(Gp:) 1
(Gp:) 2
(Gp:) N
(Gp:) 1
(Gp:) 2
(Gp:) M
(Gp:) i
(Gp:) j
(Gp:) Recorrido hacia abajo,
se va llenando el arreglo
por columnas.

20
1. Modificar el algoritmo de ordenamiento burbuja para ordenar los elementos en forma descendente.

2. Se tienen 2 arreglos unidimensionales de tamaño N, en nombre[i] y promedio[i] se almacena el nombre y el promedio del alumno i, respectivamente. Realizar un programa que liste los 10 alumnos con menor promedio.

Ayuda, considere la variable “nombre” del tipo: tipo_nombre = array[1..N] OF STRING[30]
Tarea Nº 2

21
3. Se tienen dos arreglos A y B con números enteros, de largo N y M respectivamente, los cuales están ordenados ascendentemente. Realizar un procedimiento que mezcle los dos arreglos en uno nuevo, de manera que éste también se encuentre ordenado.
Tarea Nº 2
(Gp:) 4. Usando recurrencia, calcular el i-ésimo elemento en la serie:

22
5. Se desea controlar los resultados de los alumnos en las diferentes asignaturas. Escriba un programa que lea las notas obtenidas en las distintas asignaturas. Además se debe visualizar en pantalla el nombre, calificaciones, promedio por asignatura y general de cada estudiante.
Asuma que en el curso hay 50 alumnos, y que cada uno de ellos tiene 6 asignaturas.
Tarea Nº 2